﻿#region [ License information          ]
/* ************************************************************
 *
 * Copyright (c) Bjørn Bouet Smith, 2010, 2011
 *
 * This source code is subject to terms and conditions of 
 * Microsoft Public License (Ms-PL).
 * 
 * A copy of the license can be found in the license.txt
 * file at the root of this distribution. If you can not 
 * locate the License, please send an email to bjornsmith@gmail.com
 * 
 * By using this source code in any fashion, you are 
 * agreeing to be bound by the terms of the Microsoft 
 * Permissive License.
 *
 * You must not remove this notice, or any other, from this
 * software.
 *
 * ************************************************************/
#endregion

using System.Collections.Generic;
using System.Threading;

namespace Smith.AMC.Network
{
    public class SocketQueue
    {
        class Node<T>
        {
            public T Value;
            public Pointer<T> Next;
        }

        struct Pointer<T>
        {
            public long Count;
            public Node<T> Ptr;

            /// <summary>
            /// 
            /// </summary>
            /// <param name="node">The node this pointer wraps around</param>
            /// <param name="count">The current count.</param>
            public Pointer(Node<T> node, long count)
            {
                Ptr = node;
                Count = count;
            }
        }
        private Pointer<IClientSocket> head;
        private Pointer<IClientSocket> tail;

        public SocketQueue(IEnumerable<IClientSocket> initalPool)
        {
            Node<IClientSocket> node = new Node<IClientSocket>();
            head.Ptr = tail.Ptr = node;
            foreach (IClientSocket obj in initalPool)
            {
                Enqueue(obj);
            }
        }

        /// <summary>
        /// CAS
        /// stands for Compare And Swap
        /// Interlocked Compare and Exchange operation
        /// </summary>
        /// <param name="destination"></param>
        /// <param name="compared"></param>
        /// <param name="exchange"></param>
        /// <returns></returns>
        private static bool CAS(ref Pointer<IClientSocket> destination, Pointer<IClientSocket> compared, Pointer<IClientSocket> exchange)
        {
            if (compared.Ptr == Interlocked.CompareExchange(ref destination.Ptr, exchange.Ptr, compared.Ptr))
            {
                Interlocked.Exchange(ref destination.Count, exchange.Count);
                return true;
            }

            return false;
        }

        public bool Dequeue(out IClientSocket t)
        {
            Pointer<IClientSocket> currentHead;
            t = null;
            // Keep trying until deque is done
            bool bDequeNotDone = true;
            while (bDequeNotDone)
            {
                // read head
                currentHead = head;

                // read tail
                Pointer<IClientSocket> currentTail = tail;

                // read next
                Pointer<IClientSocket> next = currentHead.Ptr.Next;

                // Are head, tail, and next consistent?
                if (currentHead.Count == head.Count && currentHead.Ptr == head.Ptr)
                {
                    // is tail falling behind
                    if (currentHead.Ptr == currentTail.Ptr)
                    {
                        // is the queue empty?
                        if (null == next.Ptr)
                        {
                            // queue is empty cannnot dequeue
                            return false;
                        }

                        // Tail is falling behind. try to advance it
                        CAS(ref tail, currentTail, new Pointer<IClientSocket>(next.Ptr, currentTail.Count + 1));

                    } // endif

                    else // No need to deal with tail
                    {
                        // read value before CAS otherwise another deque might try to free the next node
                        t = next.Ptr.Value;

                        // try to swing the head to the next node
                        if (CAS(ref head, currentHead, new Pointer<IClientSocket>(next.Ptr, currentHead.Count + 1)))
                        {
                            bDequeNotDone = false;
                        }
                    }

                } // endif

            } // endloop

            // dispose of head.ptr
            return true;
        }

        public void Enqueue(IClientSocket t)
        {
            // Allocate a new node from the free list
            Node<IClientSocket> node = new Node<IClientSocket>
            {
                Value = t
            };

            // copy enqueued value into node

            // keep trying until Enqueue is done
            bool bEnqueueNotDone = true;

            while (bEnqueueNotDone)
            {
                // read Tail.ptr and Tail.count together
                Pointer<IClientSocket> currentTail = tail;

                // read next ptr and next count together
                Pointer<IClientSocket> next = currentTail.Ptr.Next;

                // are tail and next consistent
                if (currentTail.Count == tail.Count && currentTail.Ptr == tail.Ptr)
                {
                    // was tail pointing to the last node?
                    if (null == next.Ptr)
                    {
                        if (CAS(ref currentTail.Ptr.Next, next, new Pointer<IClientSocket>(node, next.Count + 1)))
                        {
                            bEnqueueNotDone = false;
                        } // endif

                    } // endif

                    else // tail was not pointing to last node
                    {
                        // try to swing Tail to the next node
                        CAS(ref tail, currentTail, new Pointer<IClientSocket>(next.Ptr, currentTail.Count + 1));
                    }

                } // endif

            } // endloop
        }

    }
}